1. Field of the Invention
The present invention relates to a method and apparatus for hierarchically approximating shape data with an image, in which the data amount is reduced by reducing the complexity of the shape of a geometric model which is used in generating CG (Computer Graphics), thereby enabling the CG to be drawn at a high rate of speed. The invention also relates to a method and apparatus for hierarchically approximating shape data with an image, which is suitable for use in a game using CG, VR (Virtual Reality), designing, and the like since a shape which was approximated so as not to give a sense of incongruity is changed.
2. Description of the Prior Art
When drawing using a model as part of computer graphics, the same model may be used repeatedly. For example, as shown in FIG. 14, a detailed original model having data of 100% is formed and the CG is drawn on a display by using it repeatedly. When the model is arranged in a far position in a picture plane and is rendered smaller, the same model still is used, and the degree of details of the model is not changed. Therefore, the time required for the drawing depends on the degree of detail of the model and the number of models.
However, when the observer pays no attention to the model because the model is minimized and looks smaller on the picture plane or the model is out of a target point of the picture plane, it is not always necessary to draw by using the model having a high degree of detail. That is, by using a similar model in which a degree of detail is decreased to a certain extent by using a method of reducing the number of vertices of the model, reducing the number of planes of a polygon, or the like, it can appear as if the same model is used. FIG. 15 shows such an example. When the model is to appear at a distance and its size on the picture plane is small, as shown in the example, it is sufficient to draw the CG by using models in which data is reduced to, for example, 50% or 25% from that of the original model and for which the degree of detail is reduced. By using a model having a data amount smaller than that of the original model as mentioned above, a high drawing speed can be realized.
Such an approximation of the model is useful for the drawing of the CG display as mentioned above. However, if the data amount of the model is simply reduced by approximating the details of the model, the observer feels incongruity when he sees the approximated model. If this sense of incongruity can be suppressed, requests for both of the drawing speed and the drawing quality can be satisfied. For this purpose, it is desirable to reduce the data amount in a manner such that a general characteristic portion of the model is left and the other portions are reduced. Hitherto, such an approximation of the model is often executed by the manual work of a designer, so that much expense and time are necessary for the above work.
A method of obtaining a more realistic image by adhering a two-dimensional image to a plane of a model as a drawing target is generally used. This is called a texture mapping, The image that is adhered in this instance is called a texture. When the approximation of the shape as mentioned above is executed to the model which was subjected to the texture mapping, it is necessary to also pay attention to the texture adhered to the model plane. That is, it is necessary to prevent a deterioration in the appearance of the model due to a deformation of the texture shape at the time of approximation and to prevent the occurrence of a problem such that the amount of work is increased since the texture must be again adhered to the approximated model.
In past studies, according to Francis J. M. Schmitt, Brian A. Barsky, and Wen-Hui Du, xe2x80x9cAn Adaptive Subdivision Method for Surface-Fitting from Sampled Dataxe2x80x9d, Computer Graphics, Vol. 20, No. 4, August, 1986, although the shape is approximated by adhering the Bezier patch to a three-dimensional shape, there is a problem in that a general polygon is not a target.
According to Greg Turk, xe2x80x9cRe-Tiling Polygonal Surfacexe2x80x9d, Computer Graphics, Vol. 26, No. 2, July, 1992, a trial of hierarchically approximating a polygon model is executed. There is, however, a problem in that although the algorithm in the above paper can be applied to a round shape, it is not suitable for a square shape and a general shape is not a target. Further, it is not considered to approximate the shape on the basis of characteristic points of the object shape.
Further, according to Hugues Hoppe et al., xe2x80x9cMesh Optimizationxe2x80x9d, Computer Graphics Proceedings, Annual Conference Series, SIGGRAPH 1993, a model is approximated in a manner such that energy is introduced to an evaluation of the approximated model, and operations for removing the edge, dividing the patch, and swapping the edge are repeated so as to minimize the energy. According to the method of the paper, however, it is necessary to execute a long repetitive calculation until the minimum point of the energy is determined. In addition, a solving method such as a simulated annealing or the like is necessary in a manner similar to other energy minimizing problems so as not to reach a local minimum point. There is no guarantee that the energy minimum point is always visually the best point.
Further, in those papers, no consideration is made up to the texture adhered to the model upon approximation. Consequently, the method of approximating the model according to the methods in the papers has a problem in that double processes are required in which the texture is newly adhered to the approximated model after the approximation.
As mentioned above, the past studies have problems regarding the approximation of a model when a polygon is drawn. That is, the conventional method has problems such that application of the shape approximation is limited, a long calculation time is necessary for approximation, and the approximation in which required characteristic points are considered is not executed. The approximation of figure data to realize a switching of continuous layers, in which the sense of incongruity to be given to the observer at the time of the switching of the approximated model is considered, is not executed.
When the approximation is executed to the geometric model to which the texture is adhered, there is a problem in that a measure to prevent a quality deterioration after the approximation, by keeping the shape of the texture adhered to the model, is not taken. There is also a problem in that a measure to eliminate the necessity to newly adhere the texture after the approximation is not taken. Further, there is a problem that the approximation in which the existence of the texture itself is considered is not executed.
It is, therefore, an object of the invention to provide a method and apparatus for hierarchically approximating figure data with an image in the drawing of CG so that high-speed drawing is performed while maintaining a quality of the drawing.
It is another object of the invention to provide a method and apparatus for hierarchically approximating figure data with an image as if the approximation of a geometric model is performed in consideration of the existence of a texture itself.
According to the invention, in order to solve the above problems, there is provided a hierarchical approximating method of shape data for approximating shape data to data of a desired resolution, comprising the steps of: evaluating an importance of each of the edges which construct the shape data; removing an unnecessary edge on the basis of a result of the edge evaluation; and determining a vertex position after the unnecessary edge was removed.
According to the invention, in order to solve the above problems, there is provided a hierarchical approximating method of shape data with an image for approximating shape data to which image data was adhered to data of a desired resolution, comprising the steps of: determining which edge in the shape data should be removed upon approximation; determining a new vertex position in the shape data after the edge removal performed on the basis of the edge removal determination; and removing an unnecessary vertex in the image data adhered to the shape data in accordance with outputs from the edge removal determining step and the vertex movement determining step and moving a vertex on the image data in accordance with the new vertex position in the shape data.
According to the invention, in order to solve the above problems, there is provided an approximating apparatus for figure data for approximating shape data to that of a desired resolution, comprising: evaluating means for evaluating an importance of each of the edges which construct the shape data; edge removing means for removing an unnecessary edge on the basis of a result of the edge evaluation; and vertex position determining means for determining a vertex position after the unnecessary edge was removed.
According to the invention, in order to solve the above problems, there is provided a hierarchical approximating apparatus for figure data with image data for approximating shape data to which image data is adhered to data of a desired resolution, comprising: edge removal determining means for determining which edge in the shape data is removed upon approximation; vertex movement determining means for determining a new vertex position in the shape data after the edge removal; and image data removal and movement determining means for removing an unnecessary vertex in the image data adhered to the shape data in accordance with outputs from the edge removal determining means and the vertex movement determining means and for moving the vertex on the image data in accordance with the new vertex position in the shape data.
According to the invention as mentioned above, the importance of each of the edges of the shape data is evaluated, the unnecessary edge is removed on the basis of the evaluation, a new vertex after the edge removal is determined, and further, the vertex is moved on the image data in accordance with the new vertex position. Thus, the shape data can be approximated so that the change in shape is little while suppressing the deterioration of the image data adhered to the shape model.
The above and other objects and features of the present invention will become apparent from the following detailed description and the appended claims with reference to the accompanying drawings.